package com.datastructures2.graph.有向图;

import com.datastructures2.graph.最短路径.DirectedEdge;
import com.datastructures2.graph.最短路径.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;

/**
 * 寻找有向环
 * @author MaoLin Wang
 * @date 2020/2/2214:25
 */
public class DirectedCycle {
    private boolean[]marked;
    private int[] edgeTo;
    /**
     * 有向环中的所有顶点（如果存在）
     */
    private Stack<Integer>cycle;

    /**
     * 递归调用的栈上的所有顶点
     */
    private boolean[] onStack;

    public DirectedCycle(Digraph digraph) {
        marked=new boolean[digraph.V()];
        edgeTo=new int[digraph.V()];
        onStack=new boolean[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]){
                dfs(digraph,v);
            }
        }
    }

    /**
     * 使用不带权的Digraph
     * @param digraph
     * @param v
     */
    private void dfs(Digraph digraph, int v) {
        onStack[v]=true;
        //0-1-2-5-4-3
        marked[v]=true;
        for (int w: digraph.adj(v)){
            if (this.hasCycle()){
                return;
            } else if (!marked[w]){
                edgeTo[w]=v;
                dfs(digraph,w);
            }else if (onStack[w]){
                cycle=new Stack<>();
                for (int x = v; x != w; x=edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v]=false;

    }
    public Iterable<Integer>cycle(){
        return cycle;
    }
    public boolean hasCycle(){
        return cycle!=null;
    }

    public static void main(String[] args) {
        Digraph digraph=new Digraph(6);
        digraph.addEdge(0,1);
        digraph.addEdge(2,5);
        digraph.addEdge(5,4);
        digraph.addEdge(4,3);
        digraph.addEdge(3,5);
        digraph.addEdge(1,2);
        //存在环3>1->2>3
        DirectedCycle cycle = new DirectedCycle(digraph);
        if (cycle.hasCycle()){
            System.out.println("存在环");
            Stack<Integer> stack = cycle.cycle;
            while (!stack.isEmpty()){
                System.out.println(stack.pop());
            }
        }
    }
}
